package day01;

import java.util.Arrays;

/**
 * Created by MGL on 2017/3/16.
 */
public class MyHashMap<K, V> implements MyMap<K, V> {
    //默认的初始容量的大小
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
    // 默认的负载因子的大小
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    //最大容量
    static final int MAXIMUM_CAPACITY = 1 << 30;
    //键值对的数量
    transient int size;
    //定义一个阀值 创建数组的长度*负载因子的大小
    int threshold;
    //初始化负载因子的大小
    final float loadFactor;

    //定义一个 Entry 数组
    transient Node<K, V>[] table;
    //记录数组的长度
    int initialCapacity;

    //构造函数
    public MyHashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        this.initialCapacity = DEFAULT_INITIAL_CAPACITY;
        this.threshold = (int) (DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
    }

    public MyHashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    public MyHashMap(int initialCapacity, float loadFactor) {
        this.loadFactor = initialCapacity;
        //initialCapacity 为通过各种计算 获取大于 initialCapacity 那个2^n 倍的那个数
        int newInitialCapacity = getNewInitialCapacity(initialCapacity);
        this.initialCapacity = newInitialCapacity;
        this.threshold = (int) (newInitialCapacity * loadFactor);
    }

    private int getNewInitialCapacity(int initialCapacity) {
        int n = initialCapacity - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return n > MAXIMUM_CAPACITY ? MAXIMUM_CAPACITY : n + 1;
    }

    /**
     * 计算 key 的 Hash 值
     *
     * @param key
     * @return
     */
    public int hash(K key) {
        return key.hashCode();
    }

    /**
     * 通过Hash值计算 key 所在的坐标
     *
     * @param hash
     * @return
     */
    public int indexFor(int hash) {
        return hash % (table.length - 1);
    }

    /**
     * 获取键值对
     *
     * @param key
     * @return
     */
    @Override
    public V get(K key) {
        // 计算在数组中的位置
        if (table != null && table.length > 0 && key != null) {
            int index = indexFor(hash(key));
            Node<K, V>[] tab;
            Node<K, V> node;
            if ((tab = table) != null && tab.length > 0) {
                node = tab[index];
                while (node != null) {
                    if (key != null && key.equals(node.key)) {
                        return node.value;
                    }
                    node = node.next;
                }
            }
        }
        return null;
    }

    /**
     * 储存键值对
     *
     * @param key
     * @param value
     * @return
     */
    @Override
    public V put(K key, V value) {
        if (table == null) {
            this.table = resize();
        }

        int index = indexFor(hash(key));
        if (table[index] == null) {
            Node<K, V> node = new Node<K, V>(key, value, null);
            this.table[index] = node;
        } else {
            Node<K, V> node = table[index];
            Node<K, V> next = node;
            for (; next != null; ) {
                node = next;
                if (key.equals(node.key)) {
                    V oldValue = node.value;
                    node.value = value;
                    return oldValue;
                }
                next = node.next;
            }
            Node<K, V> newNode = new Node<K, V>(key, value, null);
            node.next = newNode;

        }
        if (++size > this.threshold) {
            resize();
        }
        return null;
    }

    @Override
    public int getSize() {
        return this.size;
    }

    /**
     * 进行扩容
     *
     * @return
     */
    private Node<K, V>[] resize() {
        if (table == null) {
            return new Node[this.initialCapacity];
        }
        //重新Hash值
        int n = table.length;
        Node[] newTable = new Node[n * 2];
        for (int i = 0; i < n; i++) {
            if (table[i] != null && n > 0 && table[i].next == null) {
                int index = indexFor(hash(table[i].key));
                newTable[index] = table[i];
            } else if (table[i] != null && n > 0 && table[i].next != null) {
                Node<K, V> node = table[i];
                Node<K, V> loHead = null, loTail = null;
                Node<K, V> hiHead = null, hiTail = null;
                Node<K, V> next;
                do {
                    next = node.next;
                    int hash = hash(node.key);
                    if ((hash & n) == 0) {
                        if (loHead == null) {
                            loHead = node;
                        } else {
                            loTail.next = node;
                        }
                        loTail = node;

                    } else {
                        if (hiHead == null) {
                            hiHead = node;
                        } else {
                            hiTail.next = node;
                        }

                        hiTail = node;
                    }
                } while ((node = node.next) != null);

                if (loHead != null) {
                    hiTail.next = null;
                    newTable[i] = loHead;
                }

                if (hiHead != null) {
                    hiHead.next = null;
                    newTable[i + n] = hiHead;
                }
            }
        }
        //执行使用旧的 table 通过重新计算坐标进行重新赋值
        //省略n多步骤
        table = newTable;
        return newTable;
    }

    static class Node<K, V> implements MyMap.Entry<K, V> {
        final K key;
        V value;
        Node next;

        public Node(K key, V value, Node next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }


        @Override
        public K getKey() {
            return this.key;
        }

        @Override
        public V getValue() {
            return this.value;
        }

        @Override
        public void setValue(V value) {
            this.value = value;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "key=" + key +
                    ", value=" + value +
                    ", next=" + next +
                    '}';
        }
    }

    @Override
    public String toString() {
        return "day01.MyHashMap{" +
                "table=" + Arrays.toString(table) +
                '}';
    }
}
